package com.cat.greedyAlgorithm;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/super-washing-machines/
 * @create 2025/10/9 12:11
 * @since JDK17
 */

public class Solution62 {
    public int findMinMoves(int[] machines) {
        int sum = Arrays.stream(machines).sum(), n = machines.length, ans = 0, ave = sum / n;
        if (sum % n != 0) {
            return -1;
        }
        int left = 0, rightDiff = 0, diff = 0, leftDiff = 0;
        for (int i = 0; i < n; i++) {
            leftDiff = i * ave - left;
            rightDiff = (n - i - 1) * ave - (sum - left - machines[i]);
            if (leftDiff > 0 && rightDiff > 0) {
                diff = leftDiff + rightDiff;
            } else {
                diff = Math.max(Math.abs(leftDiff), Math.abs(rightDiff));
            }
            ans = Math.max(ans, diff);
            left += machines[i];    // 左侧的值
        }

        return ans;
    }
}
